class Solution(object):
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        self.createHeap(nums)
        while k-1 > 0:
            nums[0] = nums[-1]
            nums = nums[:-1]
            self.updateHeap(nums, 0)
            k -= 1
        return nums[0]

    def updateHeap(self, nums, p):
        nums_len = len(nums)
        while p < nums_len:
            if 2*p+2 < nums_len:
                if nums[p] >= nums[2*p+1] and nums[p] >= nums[2*p+2]:
                    break
                if nums[p] < nums[2*p+2] and nums[2*p+1] < nums[2*p+2]:
                    t = nums[p]
                    nums[p] = nums[2*p+2]
                    nums[2*p+2] = t
                    p = 2 * p + 2
                elif nums[p] < nums[2*p+1]:
                    t = nums[p]
                    nums[p] = nums[2*p+1]
                    nums[2*p+1] = t
                    p = 2 * p + 1
                else:
                    break
            elif 2*p+1 < nums_len and nums[p] < nums[2*p+1]:
                t = nums[p]
                nums[p] = nums[2*p+1]
                nums[2*p+1] = t
                p = 2 * p + 1
            else:
                break

    def createHeap(self, nums):
        nums_len = len(nums)
        p = int(nums_len/2) - 1
        while p >= 0:
            if 2*p+2 < nums_len:
                if nums[p] <= nums[2*p+2] and nums[2*p+1] < nums[2*p+2]:
                    t = nums[p]
                    nums[p] = nums[2*p+2]
                    nums[2*p+2] = t
                    self.updateHeap(nums, 2*p+2)
                elif nums[p] < nums[2*p+1]:
                    t = nums[p]
                    nums[p] = nums[2*p+1]
                    nums[2*p+1] = t
                    self.updateHeap(nums, 2*p+1)
            else:
               if nums[p] < nums[2*p+1]:
                    t = nums[p]
                    nums[p] = nums[2*p+1]
                    nums[2*p+1] = t
                    self.updateHeap(nums, 2*p+1)
            p -= 1

s = Solution()
nums = [3,2,1,5,6,4]
k = 2
result = s.findKthLargest(nums, k)
print(result)

nums = [3,2,3,1,2,4,5,5,6]
k = 4
result = s.findKthLargest(nums, k)
print(result)

